/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhong
 *
 */
public class SplitArrayintoFibonacciSequence {
	List<Integer> res;
	int maxIntLen = 10;// int取值范围不超过10位

	public List<Integer> splitIntoFibonacci(String S) {
		res = new ArrayList<Integer>();
		helper(S, 0, -1, -1);
		return res;
	}

	private boolean helper(String s, int i, int a, int b) {
		if (i == s.length()) {// 成功分割
			return true;
		}
		if (a == -1) {
			if (s.charAt(i) == '0') {
				res.add(0);
				if (helper(s, i + 1, 0, b)) {
					return true;
				} else {
					res.remove(res.size() - 1);
				}
			} else {
				int end = s.length() / 2;
				end = Math.min(end, i + maxIntLen);
				for (int j = i; j < end; j++) {
					long tmp = Long.parseLong(s.substring(i, j + 1));
					if (tmp > Integer.MAX_VALUE) {
						continue;
					}
					a = (int) tmp;
					res.add(a);
					if (helper(s, j + 1, a, b))// 这个能成功分割
						return true;
					res.remove(res.size() - 1);
				}
			}

		} else if (b == -1) {
			if (s.charAt(i) == '0') {
				res.add(0);
				if (helper(s, i + 1, a, 0)) {
					return true;
				} else {
					res.remove(res.size() - 1);
				}
			} else {
				int alen = String.valueOf(a).length();
				int end = s.length() - alen;
				end = Math.min(end, i + maxIntLen);
				for (int j = i; j < end; j++) {
					long tmp = Long.parseLong(s.substring(i, j + 1));
					if (tmp > Integer.MAX_VALUE) {
						continue;
					}
					b = (int) tmp;
					res.add(b);
					if (helper(s, j + 1, a, b))
						return true;
					res.remove(res.size() - 1);
				}
			}
		} else {
			if (s.charAt(i) == '0') {
				if (a == 0 && b == 0) {
					res.add(0);
					if (helper(s, i + 1, 0, 0)) {
						return true;
					} else {
						res.remove(res.size() - 1);
					}
				}
				return false;// 只有可能ab都是0才有true
			}
			long cTmp = (long) a + b;
			if (cTmp > Integer.MAX_VALUE)
				return false;
			int c = (int) cTmp;
			String cString = String.valueOf(c);
			int clen = cString.length();
			if (i + clen <= s.length() && s.substring(i, i + clen).equals(cString)) {
				res.add(c);
				if (helper(s, i + clen, b, c)) {
					return true;
				} else {
					res.remove(res.size() - 1);
				}
			} else {
				return false;
			}
		}
		return false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String string = "0000";
		System.out.println(new SplitArrayintoFibonacciSequence().splitIntoFibonacci(string));
	}

}
